It is often important to simulate physical objects using computer models to analyze or demonstrate their behavior. One common application for such computer models is gaming, in which objects of various types are made to interact with one another in a simulated, three-dimensional universe that acts in predictable ways according to physical laws. A common occurrence in games is the collision of an object with another object (i.e. an inter-collisions), or with parts of itself (i.e. a self-collisions). In collisions involving impenetrable objects, it is important that no object penetrate or pass through another.
With the increasing visual sophistication of games, faithful rendition of thin objects, such as clothing or thin sheets of matter, has become important. Such thin objects will be referred to herein as “cloth.” Multi-layered clothing worn by a game character, for example, can involve a complex set of inter-collisions and self-collisions. Faithful simulation of thin objects, called “cloth simulation,” requires not only that pieces of the objects do not pass through each other, but also that their collisions convey a visual experience consistent with their thinness. The same considerations apply to surfaces of three-dimensional objects, if the perception of their sharpness is important in a specific context.
In one method, objects are represented with particles taking the form of spheres of positive volume, each centered on a point in a grid. Each particle has a position and a velocity. At any time step in the simulation, if a point representing another object or a piece of the same object enters the sphere representing a point on the object, a collision has occurred. Adjustments are then made to the positions of the particles involved to ensure that they do not pass through each other. In “Solid Simulation with Oriented Particles,” ACM Transactions on Graphics (SIGGRAPH 2011), 30(4), pp 92:1-92:10, Müller et al. employed particles that carry orientation and rotation, in addition to position and velocity. Such particles improve shape-matching and mesh skinning. In addition, they may be implemented using anisotropic objects, which can approximate surfaces more closely than spheres. Müller et al. teach the use of ellipsoids as oriented particles.